Comptage de chaînes (graphe non orienté) - Exemple

Prenons le graphe ci-dessous.

Sa matrice d'adjacence est  $A=\left(\begin{array}{ccccc}0& 1& 0& 0& 0\\ 1& 0& 1& 1& 1\\ 0& 1& 0& 1& 0\\ 0& 1& 1& 0& 1\\ 0& 1& 0& 1& 0\end{array}\right)$

$M=A^3=\left(\begin{array}{ccccc}0& 4& 1& 2& 1\\ 4& 4& 6& 6& 6\\ 1& 6& 2& 5& 2\\ 2& 6& 5& 4& 5\\ 1& 6& 2& 5& 2\end{array}\right)$

On lit donc (coefficients  $m_{1,4}=m_{4,1}$ ) qu'il y a une seule chaîne de 3 arêtes qui relie les sommets 1 et 4 ; il s'agit de la chaîne 1 - 2 - 4 - 3.

On lit aussi (coefficients  $m_{3,4}=m_{4,3}$ ) qu'il y a cinq chaînes de longueur 3 qui relient les sommets 3 et 4. 

Listons-les ci-dessous :

• 3 - 4 - 3 - 4
• 3 - 2 - 5 - 4
  
• 3 - 4 - 2 - 4
• 3 - 4 - 5 - 4
• 3 - 2 - 3 - 4

Remarques

• Comme le graphe n'est pas orienté, la matrice  $A$  et toutes ses puissances sont symétriques.
• Certaines de ces chaînes utilisent plusieurs fois la même arête.